package Algorithm.dfs;

import java.util.HashSet;

/**
 * 改变一个格子后最少岛屿数
 * 题目简述：01二维矩阵构成的海洋陆地，1表示陆地，上下左右相邻的陆地则表示在同一个岛屿。求最多将一个海洋格子变为陆地后的最少岛屿数
 */
public class MinIslandsAfterChange {

    public static void main(String[] args) {
        System.out.println(new MinIslandsAfterChange().minIslandsAfterChange(new int[][]{{1, 1, 0, 0},
                                                                                         {0, 0, 1, 1},
                                                                                         {1, 0, 0, 0}}));
    }

    /**
     * 思路：遍历二维数组，遇到1则进入dfs遍历完整岛屿，并将该岛屿内网格的数值改为当前岛屿id（岛屿id从2开始递增）。
     *      最后再遍历这个二维数组，看一个0格上下左右最多的岛屿数有几个。
     */
    int minIslandsAfterChange(int[][] nums) {
        int m = nums.length;
        int n = nums[0].length;
        int id = 1;
        for (int i = 0;i < m;i++) {
            for (int k = 0; k < n; k++) {
                if (nums[i][k] == 1)
                    dfs(nums, i, k, ++id); //dfs遍历完整岛屿
            }
        }
        int islandsNum = id - 1; //岛屿总数
        int max = 0;
        for (int i = 0;i < m;i++) { //遍历检查一个海洋格子周边最多的岛屿数量
            for (int k = 0; k < n; k++) {
                if (nums[i][k] == 0) {
                    HashSet<Integer> set = new HashSet<>();
                    if (i > 0 && nums[i-1][k] != 0) set.add(nums[i-1][k]);
                    if (i < m-1 && nums[i+1][k] != 0) set.add(nums[i+1][k]);
                    if (k > 0 && nums[i][k-1] != 0) set.add(nums[i][k-1]);
                    if (k < n-1 && nums[i][k+1] != 0) set.add(nums[i][k+1]);
                    max = Math.max(set.size(), max);
                }
            }
        }
        return islandsNum - max + 1; //有max个岛屿可以合成一个岛屿
    }

    /**
     * dfs遍历并标记岛屿id
     */
    void dfs(int[][] nums, int i, int k, int id) {
        if (i < 0 || i >= nums.length || k < 0 || k >= nums[0].length) return; //超过边界返回
        if (nums[i][k] != 1) return; //非未遍历陆地返回
        nums[i][k] = id;
        dfs(nums, i-1, k, id);
        dfs(nums, i+1, k, id);
        dfs(nums, i, k-1, id);
        dfs(nums, i, k+1, id);
    }
}
